from functools import cache


class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        MOD = 10 ** 9 + 7
        n = len(num2)
        num1 = num1.zfill(n)

        # limit_low:表示前面填的数字，是否达到了前面的下界
        # limi_high：表示前面填的数字，是否达到了前面的上界
        # is_num： 表示是否填了数字，True：填了数字(没跳过)，False:没填数字（前面都跳过了）
        @cache
        def f(i, cur_sum, limit_low, limit_high, is_num):
            if i == n:
                return int(is_num and min_sum <= cur_sum <= max_sum)
            res = 0
            # 处理前面都没填的情况，要求当前位的下界=='0'，是因为如果当前位不为0(为1)，跳过当前位，导致越界，小于给定的下界
            if not is_num and num1[i] == '0':
                res += f(i + 1, cur_sum, True, False, False)

            # 第i位数字，可以从哪枚举
            lo = int(num1[i]) if limit_low else 0
            hi = int(num2[i]) if limit_high else 9

            d0 = lo if is_num else max(1, lo)  # 前面是否填了数字，前面没填数字，就
            for d in range(d0, hi + 1):
                new_sum = cur_sum + d
                if new_sum > max_sum:  # 剪枝
                    continue
                res += f(i + 1, new_sum, limit_low and d == lo, limit_high and d == hi, True)
                res %= MOD
            return res % MOD

        return f(0, 0, True, True, False)